package RECUR_1028;

import java.util.Deque;
import java.util.LinkedList;

import LCommon.TreeNode;

public class Solution {
	public TreeNode recoverFromPreorder(String s) {
		Deque<TreeNode> path = new LinkedList<TreeNode>();
		int pos = 0;
		while (pos < s.length()) {
			int level = 0;
			while (s.charAt(pos) == '-') {
				level++;
				pos++;
			}
			int value = 0;
			while (pos < s.length() && Character.isDigit(s.charAt(pos))) {
				value = value * 10 + (s.charAt(pos) - '0');
				pos++;
			}
			TreeNode node = new TreeNode(value);
			if (level == path.size()) {
				if (!path.isEmpty()) {
					path.peek().left=node;
				}
			}else {
				while (level != path.size() ) {
					path.pop();
				}
				path.peek().right=node;
			}
			path.push(node);
		}
		while (path.size()>1) {
			path.pop();
		}
		return path.peek();
	}
}
